/*
 * @Author: Tendo 
 * @Date: 2021-11-18 22:22:00 
 * @Last Modified by: Tendo
 * @Last Modified time: 2021-11-18 22:41:03
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
 var permute = function (nums) {
    let res = []
    let path = []
    // 把使用过的数据放到该数组
    back([])
    return res

    function back(used) {
        // 终止条件：
        // 当收集元素的数组path的大小达到和nums数组一样大的时候
        // 说明找到了一个全排列，也表示到达了叶子节点。
        if (path.length === nums.length) {
            res.push([...path])
            return
        }

        for (let i = 0; i < nums.length; i++) {
            // path里已经收录的元素，直接跳过
            if (used[nums[i]]) {
                continue;
            }
            // 使用后设置为 true
            used[nums[i]] = true
            // 放入 path 中
            path.push(nums[i])
            // 下标走到下一个
            back(used)
            // 回溯
            path.pop()
            // 记得换枝时才清空used
            used[nums[i]] = false
        }
    }
};